<?
// <meta http-equiv="Content-Type" content="text/html; charset=utf-8">

function make_trie(&$str_val_list, $option=array())
{
	$trie = array();
	foreach ( $str_val_list as $str => $val) {
	
		$token_array = tokenize_string($str, $option);

		$full_idx = "";
		foreach ( $token_array as $token ) {
			$idx = addslashes($token['str']);
			$full_idx .= "['{$idx}']";
		}
		$cmd = "\$trie{$full_idx}['_val'] = \$val;";
		$pass = eval($cmd);
		if ( $pass === false ) echo "\n<br>create error: $full_idx";
	}
	return $trie;
}

function tokenize_string($string, $option=array())
{
	$token_array = array();
	$rpos_list = array();

	if ( !$string ) return $token_array;

	$token_pattern = '(\W)';
	preg_match_all($token_pattern, $string, $out, PREG_OFFSET_CAPTURE|PREG_SET_ORDER);
	if ( count($out) >= 1 ) { 
		foreach ( $out as $match ) {
			$word = $match[0][0];
			$lpos = $match[0][1];
			if ( $lpos > 0 ) $rpos_list[$lpos-1] = $word;	
			$rpos_list[$lpos] = $word;						
		}
	}
	$rpos_list[strlen($string)-1] = true;

	if ( $option['split_digit'] ) {
		$token_pattern = '(\d+)';	// any decimal digit 
		preg_match_all($token_pattern, $string, $out, PREG_OFFSET_CAPTURE|PREG_SET_ORDER);
		if ( count($out) >= 1 ) { 
			foreach ( $out as $match ) {
				$lpos = $match[0][1];
				if ( $lpos > 0 ) $rpos_list[$lpos-1] = 'digit';	// spliting "a12", not "12a"
				$len = strlen($match[0][0]);
				$rpos_list[$lpos+$len-1] = 'digit';
			}
		}
	}
		
	if ( $option['using_variable'] ) {
		$nonsplit_list = array();
		$token_pattern = '(\{\#(.*?)\})';
		preg_match_all($token_pattern, $string, $out, PREG_OFFSET_CAPTURE|PREG_SET_ORDER);
		if ( count($out) >= 1 ) { 
			foreach ( $out as $match ) {
				$lpos = $match[0][1];
				$rpos = $lpos + strlen($match[0][0]) - 1;
				for ( $k = $lpos ; $k < $rpos ; $k++ ) $nonsplit_list[$k] = true;
			}
		}

		$trpos_list = $rpos_list;
		foreach ( $trpos_list as $rpos => $rpos_val ) {
			if ( $nonsplit_list[$rpos] ) unset($rpos_list[$rpos]);
		}
	}

	ksort($rpos_list);
	$lpos = 0;
	foreach ( $rpos_list as $rpos => $word_splitter ) {
		$len = $rpos - $lpos + 1;
		$str = substr($string, $lpos, $len);
		$str = trim($str);
		if ( strlen($str) ) $token_array[] = array('str'=>$str, 'lpos'=>$lpos, 'rpos'=>$rpos);
		$lpos = $rpos+1;
	}
	
	return $token_array;
}

function find_set_relation($pos_array1, $pos_array2)
{
	$greater_than = true;
	if ( count($pos_array1) < count($pos_array2) ) {
		$pos_array3 = $pos_array1;
		$pos_array1 = $pos_array2;
		$pos_array2 = $pos_array3;
		$greater_than = false;
	}
	
	$pos_list1 = array();
	$pos_list2 = array();
	foreach ( $pos_array1 as $pos ) $pos_list1[$pos] = true;
	foreach ( $pos_array2 as $pos ) $pos_list2[$pos] = true;
	
	$disjoint = true;
	foreach ( $pos_array2 as $pos ) if ( $pos_list1[$pos] ) $disjoint = false;

	$in = false;
	foreach ( $pos_array2 as $pos ) if ( $pos_list1[$pos] ) $in = true;
	
	$out = false;
	foreach ( $pos_array2 as $pos ) if ( !$pos_list1[$pos] ) $out = true;
	
	$overlap = false;
	if ( $in && $out ) $overlap = true;
	
	$subset = false;
	if ( $in && !$out ) $subset = true;
	
	$proper_subset = false;
	$equal = false;
	if ( $subset ) {
		foreach ( $pos_array1 as $pos ) if ( !$pos_list2[$pos] ) $proper_subset = true;
		if ( !$proper_subset ) $equal = true;
	}

	return array('disjoint'=>$disjoint, 'overlap'=>$overlap, 'subset'=>$subset, 'proper_subset'=>$proper_subset, 'equal'=>$equal, 'greater_than'=>$greater_than);
}

// Connected component (graph theory)
// http://en.wikipedia.org/wiki/Connected_component_(graph_theory)
function find_connected_component($node_list, $adjacency_matrix)
{
	$connected_component_array = array();
	
	$prev_set = array();
	$set = array();
	$done_list = array();
	foreach ( $node_list as $n1 => $n1_val ) {
		if ( $done_list[$n1] ) continue;
		
		$set[$n1] = true;
		$done_list[$n1] = true;
		$prev_set = $set;
		
		while ( true ) {
		
			foreach ( $set as $n2 => $n2_val ) {
				if ( !$adjacency_matrix[$n2] ) continue;
				foreach ( $adjacency_matrix[$n2] as $n3 => $n3_val ) {
					$set[$n3] = true;
					$done_list[$n3] = true;
				}
			}
			
			if ( count($prev_set) == count($set) ) break;
			$prev_set = $set;
		}
		$connected_component_array[] = array_keys($set);
		$set = array();
	}
	return $connected_component_array;
}
?>
